#pragma once

#include <iostream>
using namespace std;


template<class K, class V>
struct bst_node
{
    bst_node<K, V>* _left;
    bst_node<K, V>* _right;
    K _key;
    V _val;

    bst_node<K>(const K& key = K(), const V& val = V()) 
        : _key(key), _val(val), _left(nullptr), _right(nullptr)
    {}
};

template<class K, class V>
class bs_tree
{
public:
    typedef bst_node<K, V> node;

public:
    bs_tree()
        : _root(nullptr)
    {}

    bs_tree(const bs_tree& t)
        : _root(nullptr)
    {
        _root = copy(t._root);
    }

    node* copy(node* root)
    {
        if (!root)
            return;
        
        node* new_root = new node(root->_key, root->_val);
        new_root->_left = copy(root->_left);
        new_root->_right = copy(root->_right);

        return new_root;
    }

    ~bs_tree()
    {
        destroy(_root);
        _root = nullptr;
    }

    void destroy(node* root)
    {
        if (!root)
            return;

        destroy(root->_left);
        destroy(root->_right);
        delete root;
    }

    bool insert(const K& key, const V& val)
    {
        if (!_root)
        {
            _root = new node(key, val);
            return true;
        }

        node* parent = nullptr;
        node* cur = _root;

        while (cur)
        {
            if (cur->_key < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else 
            {
                return false;
            }
        }

        if (parent->_key < key)
        {
            parent->_right = new node(key, val);
        }
        else
        {
            parent->_left = new node(key, val);
        }

        return true;
    }

    bool erase(const K& key)
    {
        node* parent = nullptr;
        node* cur = _root;

        while (cur)
        {
            if (cur->_key < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else 
            {
                if (!cur->_left)
                {
                    if (!parent)
                    {
                        _root = _root->_right;
                        return true;
                    }

                    if (parent->_left == cur)
                        parent->_left = cur->_right;
                    else 
                        parent->_right = cur->_right;

                    delete cur;
                }
                else if (!cur->_right)
                {
                    if (!parent)
                    {
                        _root = _root->_left;
                        return true;
                    }

                    if (parent->_left == cur)
                        parent->_left = cur->_left;
                    else 
                        parent->_right = cur->_left;

                    delete cur;
                }
                else 
                {
                    node* minp = cur;
                    node* min = cur->_right;

                    while (min->_left)
                    {
                        minp = min;
                        min = min->_left;
                    }

                    cur->_key = min->_key;

                    if (minp->_left == min)
                        minp->_left = min->_right;
                    else 
                        minp->_right = min->_right;

                    delete min;
                }

                return true;
            }
        }

        return false;
    }

    void inorder()
    {
        _inorder(_root);
        cout << endl;
    }

    void _inorder(node* root)
    {
        if (!root)
            return;

        _inorder(root->_left);
        printf("<%d,%d> ", root->_key, root->_val);
        _inorder(root->_right);
    }


private:
    node* _root = nullptr;
};

